#!/usr/bin/env python
from copy import deepcopy
from sys import stdout
import thread

# Simple network class.
# Not very efficient, but really handy. 
class Network:
  # Constructor. 
  def __init__(self):
    self._incoming = dict(); # _incoming[dst] = src
    self._outgoing = dict(); # _outgoing[src] = dst
    self._nodes = set();
  
  # Add an edge to the network. 
  def addEdge(self,src,dst):
    # Add to the adjacency lists. 
    self._incoming.setdefault(dst,set()).add(src);
    self._outgoing.setdefault(src,set()).add(dst);
    
    # Add to list of nodes. 
    self._nodes.add(src);
    self._nodes.add(dst);
    
  # Add parent to a node. This is just a synonym for addEdge(). 
  def addParent(self,parent,child):
    self.addEdge(parent,child);
  
  # Add node to the network.
  def addNode(self,node):
    self._nodes.add(node);
    
  # Get a list of the nodes in the network.
  # The list will not contain any duplicates. 
  def getNodes(self):
    return list(self._nodes);
  
  # Tests if the network contains a node. 
  def hasNode(self,node):
    return node in self._nodes;
  
  # Get a list of parents for a node, if they exist.
  # Otherwise, returns an empty list. 
  def getParents(self,node):
    return list(self._incoming.get(node,set()));
  
  # Get a list of children of a node, if they exist.
  def getKids(self,node):
    return list(self._outgoing.get(node,set()));
  
  # Reset a network to have no nodes, no edges.
  def clear(self):
    self._incoming = dict(); 
    self._outgoing = dict(); 
    self._nodes = set();
  
  # Test for equality of networks. The edges of both networks
  # must be identical, as well as their lists of nodes. 
  def __eq__(self,other):
    return (self._incoming == other._incoming) and \
    (self._outgoing == other._outgoing) and \
    (self._nodes == other._nodes);
  
  # String representation of the network.
  def __str__(self):
    e = [];
    for node in sorted(self._nodes):
      parents = sorted(self.getParents(node));
      if not len(parents) == 0:
        e.append(str(node) + ": " + " ".join([str(i) for i in parents]));
        
    return ", ".join(e);
  
  # Construct a network from a string representation.
  def fromString(string):
    net = Network();
    pieces = [i.strip() for i in string.split(",")];
    for chunk in pieces:
      pk = [i.strip() for i in chunk.split(':')];
      child = pk[0];
      parents = pk[1].split();
      for k in parents:
        net.addEdge(k,child);
    
    return net;
    
  fromString = staticmethod(fromString);
  
  # Hash code for the network. 
  def __hash__(self):
    return hash(str(self));
  
# Base posterior class. 
class Posterior:
  # Default constructor. Sets up the thread lock, that's about it.
  def __init__(self):
    self.lock = thread.allocate_lock();
  
  # Add a score/network to the posterior. 
  def update(self,score,network):
    raise NotImplementedError;
  
  # Return an iterator over the scores.
  # Begin: best score
  # End: worst score
  def scores(self):
    raise NotImplementedError;
  
  # Return an iterator over the networks.
  # Begin: best network
  # End: worst network
  def networks(self):
    raise NotImplementedError;
  
  # Return an iterator over score/network pairs.
  # Begin: (best score, best network)
  # End: (worst score, worst network)
  def pairs(self):
    raise NotImplementedError;
  
  # Return the number of unique scores stored in the posterior.
  def numScores(self):
    raise NotImplementedError;
  
  # Return the number of networks stored in the posterior.
  def numNetworks(self):
    raise NotImplementedError;
  
  # Acquire thread safety lock.
  def acquire(self):
    self.lock.acquire();
    
  # Release thread safety lock.
  def release(self):
    self.lock.release();
    
# Posterior which stores anything you throw at it, including
# the kitchen sink.
class HungryPosterior(Posterior):
  def __init__(self):
    Posterior.__init__(self);
    self._post = list();
  
  def numScores(self):
    return len(self._post);
    
  def update(self,score,network):
    self._post.append( (float(score),deepcopy(network)) );
  
  def scores(self):
    for i,v in sorted(self._post,reverse=True):
      yield i;
    
    return;
  
  def networks(self):
    for i,v in sorted(self._post,reverse=True):
      yield v;
    
    return;
  
  def pairs(self):
    for i,v in sorted(self._post,reverse=True):
      yield i,v;
      
    return;
  
  # Prints a list of networks and their scores.
  def write(self,writeable=stdout):
    count = 0;
    writeable.write("#" + "\t" + "Network" + "\t" + "Score");
    writeable.write("\n");
    for score,net in sorted(self._post,reverse=True):
      writeable.write(str(count) + "\t" + str(net) + "\t" + str(score) + "\n");
      count += 1;

# Posterior which does not allow duplicate networks, and
# has no maximum on the number of networks to be stored.
# Watch your memory!
class UniquePosterior(Posterior):
  # Constructor. 
  def __init__(self):
    Posterior.__init__(self);
    self._post = dict();
  
  # Number of scores.
  def numScores(self):
    count = 0;
    for score in self.scores():
      count += 1;
    
    return count;
  
  # Number of networks.
  def numNetworks(self):
    count = 0;
    for net in self.networks():
      count += 1;
      
    return count;
  
  # Update with a score/network. 
  def update(self,score,network):
    self._post.setdefault(float(score),set()).add(deepcopy(network));

  # Returns an iterator over the scores. 
  def scores(self):
    for k,v in sorted(self._post.iteritems(),reverse=True):
      for i in v:
        yield k;
    
    return;
  
  # Returns an iterator over the networks.
  def networks(self):
    for k,v in sorted(self._post.iteritems(),reverse=True):
      for i in v:
        yield i;
    
    return;
  
  # Returns an iterator over score/network pairings.
  def pairs(self):
    for k,v in sorted(self._post.iteritems(),reverse=True):
      for i in v:
        yield (k,i);
    
    return;
  
  # Prints a list of networks and their scores.
  def write(self,writeable=stdout):
    count = 0;
    writeable.write("#" + "\t" + "Network" + "\t" + "Score");
    writeable.write("\n");
    for k,v in sorted(self._post.iteritems(),reverse=True):
      for i in v: 
        writeable.write(str(count) + "\t" + str(i) + "\t" + str(k) + "\n");
        count += 1;

# Posterior which allows duplicate networks, and has a size limitation.
# This posterior is useful if your search process is guaranteed never
# to generate duplicate networks. 
class MaxPosterior(Posterior):
  def __init__(self,limit=10000):
    Posterior.__init__(self);
    self.limit = limit;
    self.heap = [];
    
  def update(self,score,network):
    if (len(self.heap) < self.limit):
        heappush(self.heap,(score,deepcopy(network)));
      
    else:
      if (score > self.heap[0][0]):
        heappop(self.heap);
        heappush(self.heap,(score,deepcopy(network)));
  
  def scores(self):
    for i in sorted(self.heap,reverse=True):
      yield i[0];
    
    return;
  
  def networks(self):
    for i in sorted(self.heap,reverse=True):
      yield i[1];
    
    return;
  
  def pairs(self):
    for i in sorted(self.heap,reverse=True):
      yield i;
      
    return;
  
  def topParents(self,node,num):
    candidates = set();
    for x in self.sorted():
      if len(candidates) < num:
        for p in x[1].getParents(node):
          if len(candidates) < num:
            candidates.add(p);
          else:
            break
      else:
        break
    return candidates
  
  
